\documentclass[11pt]{ctexart}
\usepackage{tabularx}
\usepackage{array}
\usepackage{bm}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{algorithm}
\usepackage{graphicx}
%\usepackage{algorithm2e}
\usepackage{algorithmicx}
\usepackage{algpseudocode}
\usepackage{fancyhdr}
\pagestyle{fancy}

\hypersetup{hypertex=true,
	colorlinks=true,
	linkcolor=red,
	anchorcolor=blue,
	citecolor=blue}

\fancyhf{}
\chead{\textbf{计算方法}}
\fancyhead[r]{\bfseries\thepage}
\fancyhead[l]{\bfseries\rightmark}
\renewcommand{\headrulewidth}{0.4pt} % 注意不用 \setlength
\renewcommand{\footrulewidth}{0pt}

\floatname{algorithm}{算法}
\renewcommand{\algorithmicrequire}{\textbf{输入:}}
\renewcommand{\algorithmicensure}{\textbf{输出:}}
\begin{titlepage}
	\title{\Huge\textbf{计算方法作业三、四}\\}
	\author{\Large\textbf{作者}：吴润泽 \and{\Large\textbf{学号}：181860109}\\
		\\
		\and {\Large\textbf{Email}：\href{mailto:181860109@smail.nju.edu.cn}{181860109@smail.nju.edu.cn}}\\}
	\date{\Large\today}
\end{titlepage}
\begin{document}
		\maketitle
	\tableofcontents
	\newpage
	\section*{assignment I}
	\markright{assignment I}
	\addcontentsline{toc}{section}{assignment I}
	\subsection*{problem 2}
	\markright{problem 2}
	\addcontentsline{toc}{subsection}{problem 2}
	\subsubsection*{(1)}
	\noindent \textbf{证明:}\\
	对于$A_2$中的元素$a^{'}_{ij}=a_{ij}-a_{1j}
	\frac{a_{i1}}{a_{11}},(i,j=2,3,4,\dots ,n)$。\\
	由于A为对称矩阵，则$a^{'}_{ji}=a_{jj}-a_{1i}
	\frac{a_{1j}}{a_{11}}=a^{'}_{ji}$。\\即$A_2$为对称矩阵。
	\subsubsection*{(2)}
	$$
	\begin{aligned}
		&
		\begin{bmatrix}
		0.6428&0.3475&-0.8468\\
		0.3475&1.8423&0.4759\\
		-0.8468&0.4759&1.2147\\
		\end{bmatrix}
		\begin{bmatrix}
		x_1\\x_2\\x_3\\
		\end{bmatrix}
		=\begin{bmatrix}
		0.4127\\1.7321\\-0.8621\\
		\end{bmatrix}
		\\
		&\begin{bmatrix}
			0.6428&0.3475&-0.8468\\
			0&1.6544&0.9337\\
			0&0.9337&0.0992\\
			\end{bmatrix}
			\begin{bmatrix}
			x_1\\x_2\\x_3\\
			\end{bmatrix}
			=\begin{bmatrix}
			0.4127\\1.5090\\-0.3184\\
			\end{bmatrix}
		\\
		&\begin{bmatrix}
			0.6428&0.3475&-0.8468\\
			0&1.6544&0.9337\\
			0&0&-0.4278\\
			\end{bmatrix}
			\begin{bmatrix}
			x_1\\x_2\\x_3\\
			\end{bmatrix}
			=\begin{bmatrix}
			0.4127\\1.5090\\-1.1700\\
			\end{bmatrix}
	\end{aligned}
	$$
	解得$x_1=4.5867,x_2=-0.6315,x_3=2.7352$。
	\subsection*{problem 12}
	\markright{problem 12}
	\addcontentsline{toc}{subsection}{problem 12}
	\paragraph{解:}
	$$
	\begin{aligned}
		&
		\begin{bmatrix}
		2&1&-3&-1&1&0&0&0\\
		3&1&0&7&0&1&0&0\\
		-1&2&4&-2&0&0&1&0\\
		1&0&-1&5&0&0&0&1\\
		\end{bmatrix}\\
		\xrightarrow[]{}
		&\begin{bmatrix}
		3&1&0&7&0&1&0&0\\
		2&1&-3&-1&1&0&0&0\\
		-1&2&4&-2&0&0&1&0\\
		1&0&-1&5&0&0&0&1\\
		\end{bmatrix}\\	
		\xrightarrow[]{}
		&\begin{bmatrix}
		1&\frac{1}{3}&0&\frac{7}{3}&0&\frac{1}{3}&0&0\\
		0&\frac{1}{3}&-3&-\frac{17}{3}&1&-\frac{3}{2}&0&0\\
		0&\frac{7}{3}&4&\frac{1}{3}&0&\frac{1}{3}&1&0\\
		0&-\frac{1}{3}&-1&\frac{8}{3}&0&-\frac{1}{3}&0&1\\
		\end{bmatrix}\\
		\xrightarrow[]{}
		&\begin{bmatrix}
		1&0&\frac{-4}{7}&\frac{16}{7}&0&\frac{2}{7}&-\frac{1}{7}&0\\
		0&1&\frac{12}{7}&\frac{1}{7}&0&\frac{1}{7}&\frac{3}{7}&0\\
		0&0&\frac{25}{7}&-\frac{40}{7}&1&-\frac{5}{7}&-\frac{1}{7}&0\\
		0&0&-\frac{2}{7}&\frac{19}{7}&0&-\frac{2}{7}&\frac{1}{7}&1\\
		\end{bmatrix}\\
		\xrightarrow[]{}
		&\begin{bmatrix}
		1&0&0&\frac{16}{5}&-\frac{4}{25}&\frac{2}{5}&-\frac{3}{25}&0\\
		0&1&0&-\frac{13}{5}&-\frac{12}{25}&-\frac{1}{5}&\frac{9}{25}&0\\
		0&0&1&\frac{8}{5}&-\frac{7}{25}&\frac{1}{5}&\frac{1}{25}&0\\
		0&0&0&\frac{17}{5}&-\frac{3}{25}&-\frac{1}{5}&\frac{4}{25}&1\\
		\end{bmatrix}
		\xrightarrow[]{}
		\begin{bmatrix}
		1&0&0&0&-\frac{4}{85}&\frac{10}{17}&-\frac{23}{85}&-\frac{16}{17}\\
		0&1&0&0&\frac{33}{85}&-\frac{6}{17}&\frac{214}{425}&\frac{13}{17}\\
		0&0&1&0&-\frac{19}{85}&\frac{5}{17}&-\frac{3}{85}&-\frac{8}{17}\\
		0&0&0&1&-\frac{3}{85}&-\frac{1}{17}&\frac{4}{85}&\frac{5}{17}\\
		\end{bmatrix}\\
	A^{-1}=&
	\begin{bmatrix}
	-\frac{4}{85}&\frac{10}{17}&-\frac{23}{85}&-\frac{16}{17}\\
	\frac{33}{85}&-\frac{6}{17}&\frac{214}{425}&\frac{13}{17}\\
	-\frac{19}{85}&\frac{5}{17}&-\frac{3}{85}&-\frac{8}{17}\\
	-\frac{3}{85}&-\frac{1}{17}&\frac{4}{85}&\frac{5}{17}\\
	\end{bmatrix}.
	\end{aligned}
	$$
	\newpage
	\subsection*{problem 13}
	\markright{problem 13}
	\addcontentsline{toc}{subsection}{problem 13}
	\paragraph{解：}
	$$
	\begin{aligned}
	\begin{bmatrix}
	2&-1&&&\\
	-1&2&-1&&\\
	&-1&2&-1&\\
	&&-1&2&-1\\
	&&&-1&2\\
	\end{bmatrix}
	=\begin{bmatrix}
	\alpha_1&&&&\\
	-1&\alpha_2&&&\\
	&-1&\alpha_3&&\\
	&&-1&\alpha_4&\\
	&&&-1&\alpha_5\\
	\end{bmatrix}
	\begin{bmatrix}
	1&\beta_1&&&\\
	&1&\beta_2&&\\
	&&1&\beta_3&\\
	&&&1&\beta_4\\
	&&&&1\\
	\end{bmatrix}
	\end{aligned}
	$$
	根据追逐法的推导公式:
	$$
	\left\{
	\begin{aligned}
	&b_1=\alpha_1,&c_1=\alpha_1\beta_1,\\
	&b_i=\alpha_i\beta_{i-1}+\alpha_i,&i=2,3,4,5,\\
	&c_i=\alpha_i\beta_{i},&i=2,3,4,\\
	\end{aligned}
	\right.
	$$
	计算可得:
	$$
	\begin{aligned}
	&\alpha_1=2,	&\alpha_1=\frac{3}{2},	&\alpha_3=\frac{4}{3},	&\alpha_4=\frac{5}{4},	&\alpha_5=\frac{6}{5},\\
	&\beta_1=-\frac{1}{2},	&\beta_2=-\frac{2}{3},	&\beta_3=-\frac{3}{4},	&\beta_4=-\frac{4}{5}.
	\end{aligned}
	$$
	解$Ly=f$:
	$$
	\begin{aligned}
	\begin{bmatrix}
	2&&&&\\
	-1&\frac{3}{2}&&&\\
	&-1&\frac{4}{3}&&\\
	&&-1&\frac{5}{4}&\\
	&&&-1&\frac{6}{5}\\
	\end{bmatrix}
	\begin{bmatrix}
	y_1\\y_2\\y_3\\y_4\\y_5
	\end{bmatrix}=
	\begin{bmatrix}
	1\\0\\0\\0\\0
	\end{bmatrix}
	\end{aligned}
	$$
	计算可得： 
	 $
	y_1=\frac{1}{2},y_2\frac{1}{3},y_3=\frac{1}{4},
	y_4=\frac{1}{5},y_5=\frac{1}{6}.
	$\\
	解$Ux=y$:
	$$
	\begin{aligned}
	\begin{bmatrix}
	1&-\frac{1}{2}&&&\\
	&1&-\frac{2}{3}&&\\
	&&1&-\frac{3}{4}&\\
	&&&1&-\frac{4}{5}\\
	&&&&1\\
	\end{bmatrix}
	\begin{bmatrix}
	x_1\\x_2\\x_3\\x_4\\x_5
	\end{bmatrix}=
	\begin{bmatrix}
	\frac{1}{2}\\\frac{1}{3}\\\frac{1}{4}\\\frac{1}{5}\\\frac{1}{6}
	\end{bmatrix}
	\end{aligned}
	$$
	计算可得: $x_1=\frac{1}{6},x_2=\frac{1}{3},x_3=\frac{1}{2},x_4=\frac{2}{3},x_5=\frac{5}{6}.$
	\subsection*{problem 15}
	\markright{problem 15}
	\addcontentsline{toc}{subsection}{problem 15}
	\noindent \textbf{解:}\\
	\noindent 对于A，$Delta_2=0$，故A不能直接分解。但$\Delta_3=-10$，故交换A的第1行和第3行后的矩阵顺序主子式均不为0，则可以分解且分解不唯一。\\
	\noindent 对于B，$\Delta_2=0,\Delta_3=0$，故不能分解。\\
	\noindent 对于C，$\Delta_1=1,\Delta_2=5,\Delta_3=1$均不为0，故C可以分解且分解唯一。
	$$
	C=
	\begin{bmatrix}
	1&&\\ 2&1&\\ 6&3&1\\
	\end{bmatrix}
	\begin{bmatrix}
	1&2&6\\ &1&3\\ &&1\\
	\end{bmatrix}.
	$$
	\subsection*{problem 18}
	\markright{problem 18}
	\addcontentsline{toc}{subsection}{problem 18}
	\noindent \textbf{解:}\\
	行范数：$$\Vert A\Vert_{\infty}=\max \limits_{1\leq i\leq n}\sum\limits_{j=1}^{n}|a_{ij}|=1.1.$$\\
	列范数：$$\Vert A\Vert_{1}=\max \limits_{1\leq j\leq n}\sum\limits_{i=1}^{n}|a_{ij}|=0.8.$$\\
	2-范数：
	$$
	\begin{aligned}
	&A^{T}A=
	\begin{bmatrix}
	0.6&0.1\\0.5&0.3\\
	\end{bmatrix}
	\begin{bmatrix}
	0.6&0.5\\0.1&0.3\\
	\end{bmatrix}
	=\begin{bmatrix}
	0.37&0.33\\0.33&0.34\\
	\end{bmatrix}，\\
	&\lambda_{max}(A^TA)=0.6853407,\\
	&\Vert A \Vert_2=\sqrt{\lambda_{max}(A^TA)}=0.8278531.\\
	\end{aligned}
	$$
	F-范数：
	$$\Vert A\Vert_{F}=(\sum \limits_{i=1}^n a_{ij}^2)^{\frac{1}{2}}=0.842615.$$\\
	\subsection*{problem 19}
	\markright{problem 19}
	\addcontentsline{toc}{subsection}{problem 19}
	\noindent \textbf{证明:}\\
	$$
	\begin{aligned}
	\Vert x \Vert_{\infty}&=\max\limits_{1\leq i\leq n}|x_i|\leq \sum\limits_{i=1}^n|x_i|=\Vert x \Vert_1\leq \sum\limits_{i=1}^n \max\limits_{1\leq i\leq n} |x_i|
	\\&=\sum\limits_{i=1}^n \Vert x \Vert_{\infty}=n\Vert x \Vert_{\infty}.
	\end{aligned}
	$$
	故原式成立。
	\subsection*{problem 31}
	\markright{problem 31}
	\addcontentsline{toc}{subsection}{problem 31}
	\subsubsection*{a.}
	易知$\lambda(W^T)=\lambda(W),\lambda((W^T)^{-1})=\lambda(W^{-1})$，
	则$
	\lambda(A)=\lambda^2(W),\lambda(A^{-1})=\lambda^2(W^{-1}),
	\Vert A^{-1} \Vert_2=\Vert W^{-1}\Vert_2^2,	\Vert A \Vert_2=\Vert W \Vert_2^2.
	$ 从而:
	$$
	\begin{aligned}
	cond(A)_2&=\Vert A^{-1}\Vert_2\Vert A\Vert_2=\Vert W^{-1}\Vert_2^2 \Vert W \Vert_2^2\\
	&=\left[\Vert W^{-1}\Vert_2 \Vert W \Vert_2\right]^2=\left[cond(W)_2\right]^2.\\
	\end{aligned}
	$$
	\subsubsection*{b.}
	$$
	\begin{aligned}
	cond(A)_2&=\Vert A^{-1}\Vert_2\Vert A\Vert_2=\Vert W^{-1}\Vert_2^2 \Vert W \Vert_2^2\\
	&=\left(\Vert W^{-1}\Vert_2 \Vert W \Vert_2\right)\left(\Vert (W^{T})^{-1}\Vert_2 \Vert W^T \Vert_2\right)\\
	&=cond(W)_2cond(W^T)_2.\\
	\end{aligned}
	$$
	\subsection*{problem 33}
	\markright{problem 33}
	\addcontentsline{toc}{subsection}{problem 33}
	\noindent \textbf{证明:}\\
	因为A是正交矩阵，则 $A^TA=AA^T=I,A^{-1}=A^T$，则有
	$$\begin{aligned}
	&\Vert A \Vert_2=\sqrt{\lambda_{max}(A^TA)}=\sqrt{\lambda_{max}(I)}=1,\\
	&\Vert A^{-1} \Vert_2=\Vert A^{T} \Vert_2=\sqrt{\lambda_{max}(AA^T)}=\sqrt{\lambda_{max}(I)=1}\\
	\end{aligned}
	$$
	因此，$cond(A)_2=\Vert A \Vert_2\Vert A^{-1}\Vert_2=1$得证。
	
	\newpage
	\section*{assignment II}
	\markright{assignment II}
	\addcontentsline{toc}{section}{assignment II}
	\subsection*{problem 17}
	\markright{problem 17}
	\addcontentsline{toc}{subsection}{problem 17}
	\paragraph{解}
	$\int_0^1 1\mathrm{d}x=1,\int_0^1 x\mathrm{d}x=\frac{1}{2},
	\int_0^1 x^2\mathrm{d}x=\frac{1}{3},\int_0^1 x^3\mathrm{d}x=\frac{1}{4}$得。
	$$
	\begin{aligned}
		&
		\begin{bmatrix}
		1&\frac{1}{2}\\ \frac{1}{2}&\frac{1}{3}\\
		\end{bmatrix}
		\begin{bmatrix}
		a\\b\\
		\end{bmatrix}
		=\begin{bmatrix}
		\frac{1}{3}\\\frac{1}{4}\\
		\end{bmatrix}\\
	\end{aligned}
	$$
	解得$a=-\frac{1}{6},b=1$，因此$S_1^{*}(x)=-\frac{1}{6}+x$。\\
	平方误差为
	$$
	\Vert\delta\Vert_2^2=(f,f)-(S_1^{*}(x))=\frac{1}{180}\approx 0.0056.
	$$
	$\int_0^1 x^{100}\cdot x^{100}\mathrm{d}x=\frac{1}{201},
	\int_0^1 x^{100}\cdot x^{101}\mathrm{d}x=\frac{1}{202},
	\int_0^1 x^{101}\cdot x^{101}\mathrm{d}x=\frac{1}{203},$\\
	$
	\int_0^1 x^2\cdot x^{100}\mathrm{d}x=\frac{1}{103},
	\int_0^1 x^{2}\cdot x^{101}\mathrm{d}x=\frac{1}{104}$得。
	$$
	\begin{aligned}
		&
		\begin{bmatrix}
		\frac{1}{201}&\frac{1}{202}\\ \frac{1}{202}&\frac{1}{203}\\
		\end{bmatrix}
		\begin{bmatrix}
		a\\b\\
		\end{bmatrix}
		=\begin{bmatrix}
		\frac{1}{103}\\\frac{1}{104}\\
		\end{bmatrix}\\
	\end{aligned}
	$$
	解得$a\approx 375.2425,b\approx 375.1482$，因此$S_2^{*}(x)=375.2425x^{100}+375.1482x^{101}$。\\
	平方误差为
	$$
	\Vert\delta\Vert_2^2=(f,f)-(S_2^{*}(x))\approx 0.1641 .
	$$
	易得选取$\{1,x\}$为基函数，误差更小。
	\subsection*{problem 20}
	\markright{problem 20}
	\addcontentsline{toc}{subsection}{problem 20}
	\subsubsection*{解}
	$
	\begin{aligned}
		&a_0=(f(x),P_0(x))/2=\frac{1}{2}\int_{-1}^{1}\sin{\frac{x}{2}}\mathrm{d}x=0,\\
		&a_1=3(f(x),P_1(x))/2=\frac{3}{2}\int_{-1}^{1}\sin{\frac{x}{2}}\cdot x\mathrm{d}x=12\sin{\frac{1}{2}}-6\cos\frac{1}{2},\\
		&a_2=5(f(x),P_1(x))/2=\frac{5}{2}\int_{-1}^{1}\sin{\frac{x}{2}}\cdot \frac{3x^2-1}{2}\mathrm{d}x=0,\\
		&a_3=7(f(x),P_1(x))/2=\frac{7}{2}\int_{-1}^{1}\sin{\frac{x}{2}}\cdot \frac{5x^3-3x}{2}\mathrm{d}x=826\cos{\frac{1}{2}}-1512\sin\frac{1}{2},\\
	\end{aligned}\\
	$
	则三次最佳逼近多项式为
	$$
	\begin{aligned}
		S^{*}(x)&=a_1P_1(x)+a_3P_3(x)\\
		&=(12\sin{\frac{1}{2}}-6\cos\frac{1}{2})x+(826\cos{\frac{1}{2}}-1512\sin\frac{1}{2})(\frac{5x^3-3x}{2})\\
		&=(2065\cos\frac{1}{2}-3780\sin\frac{1}{2})x^3+(2280\sin{\frac{1}{2}}-1245\cos\frac{1}{2})x.
	\end{aligned}
	$$
	误差图形为
	$$
	\includegraphics[width=200pt,height=200pt]{chapter3-20.png}$$
	其均方误差为
	$$
	\begin{aligned}
		\Vert\delta_n(x)\Vert_2=\Vert\sin\frac{x}{2}-S^{*}(x)\Vert_2
		=\sqrt{\int_{-1}^1\sin^2\frac{x}{2}-\sum\limits_{k=0}^{3}\frac{2}{2k+1}a_k^2}\approx 1.3966e-05.
	\end{aligned}
	$$
	\subsection*{problem 22}
	\markright{problem 22}
	\addcontentsline{toc}{subsection}{problem 22}
	\paragraph{解}
	$\Phi=span\{1,x^2\},\varphi_0(x)=1,\varphi_1(x)=x^2,$则
	$$\begin{aligned}
		&(\varphi_0,\varphi_0)=\sum\limits_{i=1}^5 1^2=5,
		(\varphi_1,\varphi_1)=\sum\limits_{i=1}^5 x_i^4=7277699,\\
		&(\varphi_0,\varphi_1)=(\varphi_1,\varphi_0)=\sum\limits_{i=1}^5 x_i^2=5327,\\
		&(\varphi_0,y)=\sum\limits_{i=1}^5 y_i=271.4,(\varphi_1,y)=\sum\limits_{i=1}^5 x_i^2y_i=369321.5,\\
	\end{aligned}
	$$
	从而得到法方程为
	$$
	\left\{
		\begin{aligned}
			&5a+5327b=271.4\\
			&5327a+7277699b=369321.5\\
		\end{aligned}\right.
	$$
	解得$a=0.9726046,b=0.0500351$，所以公式为
	$$y=0.9726046+0.0500351 x^2.$$
	均方误差为
	$$\Vert\delta_n(x)\Vert_2=
	\sqrt{\Vert y \Vert_2^2-a(\varphi_0,y)-b(\varphi_1,y)}\approx 0.130$$
	\newpage
	\subsection*{problem 24}
	\markright{problem 24}
	\addcontentsline{toc}{subsection}{problem 24}
	\paragraph{解}
	依题目数据进行描点作图，可大致推断曲线近似为指数函数，设$y=ae^{\frac{b}{t}}$，两边取对数得，
	$$\ln y=\ln a+\frac{b}{t},$$
	记$\overline{y}=\ln y$，
	则有$$\overline{y}=\ln a+\frac{b}{t},$$
	则$\Phi=span\{1,\frac{1}{t}\},\varphi_0(x)=1,\varphi_1(x)=\frac{1}{t},$则
	$$\begin{aligned}
		&(\varphi_0,\varphi_0)=\sum\limits_{i=1}^{11} 1^2=11,
		(\varphi_1,\varphi_1)=\sum\limits_{i=1}^{11} \frac{1}{t}_i^2=0.06232136,\\
		&(\varphi_0,\varphi_1)=(\varphi_1,\varphi_0)=\sum\limits_{i=1}^{11} \frac{1}{t}_i=0.6039755,\\
		&(\varphi_0,\overline{y})=\sum\limits_{i=1}^{11} \overline{y}_i=13.639649,
		(\varphi_1,\overline{y})=\sum\limits_{i=1}^{11} \frac{\overline{y}_i}{t_i}=0.5303303,\\
	\end{aligned}
	$$
	从而得到法方程为
	$$
	\left\{
		\begin{aligned}
			&11 \ln a+0.6039755b=13.639649\\
			&0.6039755\ln a+0.06232136b=0.5303303\\
		\end{aligned}\right.
	$$
	解得$a=5.2151048,b=-7.4961692$，所以公式为
	$$y=5.2151048e^{-\frac{7.4961692}{t}}.$$
\end{document}